import java.util.Stack;

public class stack<L> {
    /**
     * 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序.
     * 假设压入栈的所有数字均不相等.
     * 例如:序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,
     * 但4,3,5,1,2就不可能是该压栈序列的弹出序列
     */
    public boolean IsPopOrder(int [] pushA, int [] popA) {
        java.util.Stack<Integer> stack = new java.util.Stack<>();
        int j = 0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while (j < popA.length && !stack.empty() && stack.peek() == popA[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
    /**
     * 定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度为O(1)
     * 注意:保证测试中不会当栈为空的时候,对栈调用pop()或者min()或者top()方法
     * 我们使用一个辅助栈,内部保存元素的个数和数据栈完全一样,不过,辅助栈内部永远保存
     * 本次入栈的数为所有数据的最小值
     *
     */
    private java.util.Stack<Integer> dataStack = new java.util.Stack<>();
    private java.util.Stack<Integer> minStack = new java.util.Stack<>();

    public void push(int node) {
        dataStack.push(node);
        if (minStack.isEmpty() || node < minStack.peek()) {
            minStack.push(node);
        }else {
            minStack.push(minStack.peek());
        }
    }

    public void pop() {
        dataStack.pop();
        minStack.pop();
    }

    public int top() {
        return dataStack.peek();
    }

    public int min() {
        return minStack.peek();
    }

    /**
     * 有效括号匹配
     * 给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
     * 括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
     */
    public boolean isVaild (String s) {
        Stack<Character> st = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                st.push(')');
            }else if (s.charAt(i) == '[') {
                st.push(']');
            }else if (s.charAt(i) == '{') {
                st.push('}');
            }else if (st.isEmpty() || st.pop() != s.charAt(i)) {
                return false;
            }
        }
        return st.isEmpty();
    }
}
